package com.review.dp;

public class LC_91 {
    /*
    分析:
        本题利用动态规划比较容易解决,但需要注意分情况讨论
        。dp[i]为str[..i]的译码方法总数
        。分情况讨论: (建立最优子结构)
            ●若s[i]='0",那么若s[i-1]= '1'or'2' ,则dp[i] = dp[i-2] ;否则return 0
            口解释: si-1]+s[i]唯一被译码 ,不增加情况
            ●若s[i-1]= 1',则dp[i] = dp[-1] + dp[i-2]
            口解释: s[i-1]与s[i]分开译码,为dp[i-1] ;合井译码,为dp[i-2]
            ●若s[i-1]=*2" and '1'<=s[i]<='6' ,则dp[i] = dp[i-1] + dp[i-2]
            口解释:同上
        。由分析可知, dp[i]仅可能与前两项有关,故可以用单变量代替dp[]数组,将空间复杂度从O(n)降到O (1)
     */
    public static int numDecodings(String s) {
        // https://leetcode-cn.com/problems/decode-ways/solution/c-wo-ren-wei-hen-jian-dan-zhi-guan-de-jie-fa-by-pr/
        int length = s.length();
        if (s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[length];
        dp[0] = 1;

        for (int i = 1; i < length; i++) {
            if (s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
                    dp[i] = dp[Math.max(i - 2, 0)];
                } else {
                    return 0;
                }
            } else if (s.charAt(i - 1) == '1') {
                dp[i] = dp[i - 1] + dp[Math.max(i - 2, 0)];
            } else if (s.charAt(i - 1) == '2' && s.charAt(i) >= '1' && s.charAt(i) <= '6') {
                dp[i] = dp[i - 1] + dp[Math.max(i - 2, 0)];
            } else {
                dp[i] = dp[i - 1];
            }

        }
        return dp[length - 1];
    }

    // 复制自力扣
    public static int numDecodings_2(String s) {
        //从后往前，识别最后两个字符
        char[] chars = s.toCharArray();
        int length = s.length();
        int[] dp = new int[length + 1];
        dp[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            if (chars[i - 1] != '0') {
                dp[i] += dp[i - 1];
            }
            if (i >= 2) {
                int t = (chars[i - 2] - '0') * 10 + chars[i - 1] - '0';
                if (t >= 10 && t <= 26) {
                    dp[i] += dp[i - 2];
                }
            }
        }
        return dp[length];
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("227"));
        System.out.println(numDecodings_2("207"));
    }
}
